1. Field of the Invention
The present invention relates to memories.
2. Description of the Related Art
Conventional communication systems include transmitters and receivers. In synchronous communication systems the transmitter and receiver are based on the same clock or timing information. Therefore, transmitted data is received with the proper timing constraints. In asynchronous communications the transmitter and receiver are based on different clocks. Therefore, the transmitter and receiver may have different time domains. As a result, there is a need to queue or resynchronize communicated data. The queuing or resynchronization of data is often accomplished with a memory. For example First-in, First-out (FIFO) memories are often used for this purpose.
A FIFO memory is a memory that processes data in the order that the data is received by the memory. In other words, data that is received first, is processed first. In a conventional FIFO memory data is written into a memory space based on a first clock and read out of the memory space based on a second clock. The writing and reading may be synchronized (e.g. synchronous communications) or unsynchronized (e.g. asynchronous communications).
An asynchronous FIFO memory includes a write counter and a read counter. The write counter is incremented each time information is written into the memory space. The read counter is incremented each time that information is read out of the memory space. The write counter and the read counter control a write pointer and a read pointer, respectively. The write pointer and the read pointer identify the location in the memory space that the data will be written to or read from. In an asynchronous FIFO, the write counter and write pointer are dependent on the transmitter time domain and the read counter and read pointer are dependent on the receiver time domain.
In conventional communication systems, techniques are implemented to ensure that the write pointer and read pointer maintain a cooperative relationship. For example, it is important that the write pointer does not point to a memory location that has not been read. It is equally important that the read pointer does not point to a memory location that has already been read from. In addition, there are a number of other scenarios that may develop if the write pointer and the read pointer are not operating in a coordinated manner.
To maintain the cooperative relationship a number of techniques have been developed. For example, forced spacing between the write pointer and the read pointer may be implemented. This would ensure that the two pointers are not writing or reading in an uncoordinated manner. Different testing algorithms may be implemented to make sure that the spaces being written into and the spaces being read from, are written into and read from, at the right time.
In addition, to complicate matters, conventional memories are made from memory storage elements such as flip-flops. Most memory storage elements take time to store data. Typically, there is time before data storage, known as the setup time and a time after the data storage, known as the hold time. If there are changes in the data input to a storage device between the setup and hold time, the data stored in the memory element is defined as unstable and as a result is unreliable. Therefore, in a FIFO memory, accommodations have to be made for the setup and hold times of the memory elements. The accommodations are typically made by establishing spacing between the write pointer and read pointer or by developing an algorithm, which ensures the coordinated operation of the write pointer and the read pointer.
Approaches for ensuring the coordinated operation of the write pointer and read pointer include methods that are implemented in the FIFO architecture and methods that are implemented in the communication systems. For example, in the FIFO architecture, one method for ensuring the coordinated operation of the write pointer and the read pointer, involves comparing the two counters associated with the two pointers, to ensure that the two pointers are appropriately spaced relative to each other. However, comparing two counters that are clocked asynchronously can lead to unreliable decoding if either or both counters change multiple bits simultaneously. Incrementing both counters according to a Gray counting sequence avoids this problem. In a Gray counting sequence only one bit in the write or read counter will change with each count. As a result, the problem of counters changing multiple bits simultaneously is avoided.
A number of methods may be implemented in a communication system to maintain coordinated operation of the write pointer and the read pointer. For example, spacing or symbols may be placed between data packets when a transmitter sends packets. The spacing between packets provides space between the data packets arriving at a memory and as a result, the read pointer has an opportunity to advance so that there is no overlap between the data that is written into the memory and the data that is read out of the memory. In addition, special symbols may be placed within the data stream. The symbols have the effect of increasing or decreasing the spacing between pointers so that the pointers continue to work in a coordinated manner.
Although some of these methods and techniques are applicable to individual communications links, a number of the newer communication systems include several communications links, each communicating information in parallel. In many of the newer communication systems, data is communicated by striping the data across each link and consolidating the data in a receiver.
Thus there is a need to coordinate the reading and writing of data from a memory, when reading is done on one time domain and writing is done on a second, different time domain. There is a need for coordination techniques that enable multiple links to synchronize data in a receiver.